using System;
using System.Diagnostics;

using FineCollection.Intf;
using FineCollection.Utils;



// ReSharper disable RedundantExtendsListEntry


namespace FineCollection.Cont
{

    /// <summary>
    /// Abstract array-based collection.
    /// </summary>
    /// <typeparam name="T">type of an item.</typeparam>
    [DebuggerDisplay("Count = {Count}")]
    [DebuggerTypeProxy(typeof(ArrBaseCollectionDebugView<>))]
    public abstract class ArrBaseCollection<T>
        : RRandomList<T>, WCollection<T>
    {

        #region STORAGE

        /// <summary>
        /// Array that holds elements.
        /// </summary>
        /// <remarks>
        /// Can be null.
        /// </remarks>
        internal T[] ar;

        /// <summary>
        /// Count of holds elements.
        /// </summary>
        internal int count;

        /// <summary>
        /// Index of the first present element.
        /// </summary>
        /// <remarks>
        /// The first index is undefined when the collection is empty.
        /// </remarks>
        internal int firstIndex;

        /// <summary>
        /// Index of the last present element.
        /// </summary>
        /// <remarks>
        /// <p>The last index is undefined when the collection is empty.</p>
        /// <p>When only one element is holded, it equals to the <see cref="firstIndex"/>.</p>
        /// </remarks>
        internal int lastIndex;

        #endregion
        


        #region CONSTRUCTORS and DESTRUCTOR

        /// <summary>
        /// Empty constructor.
        /// Creates an empty collection.
        /// </summary>
        protected ArrBaseCollection(int firstIndex)
        {
            this.firstIndex = firstIndex;
            this.lastIndex = firstIndex - 1;
            this.count = 0;
        }
        
        
        /// <summary>
        /// Creates an empty collection with the specified capacity.
        /// </summary>
        protected ArrBaseCollection(int firstIndex, int cap)
            : this(firstIndex)
        {
            EnsureCapacity(cap);
        }


        #endregion

        
        
        #region STORAGE CONTROL

        /// <summary>
        /// Expands the internal array, if it is needed, up to the specified capacity.
        /// </summary>
        /// <param name="capacity">desired capacity.</param>
        protected void EnsureCapacity(int capacity)
        {
            int oldCapacity = (ar == null) ? 0 : ar.Length;
            if (capacity <= oldCapacity)
                return; // not needed to do something

            int newCapacity = (capacity + 3) & (~3);

            if (count == 0)
                ar = new T[newCapacity];
            else
                Array.Resize(ref ar, newCapacity);
        }


        /// <summary>
        /// Reduces size of the internal array to make it exctly equal to <see cref="Count"/>.
        /// If no items, drops the internal array.
        /// </summary>
        protected void Shrink()
        {
            if (count == 0)
            {
                ar = null;
            }
            else
            {
                if (ar.Length > count)
                    Array.Resize(ref ar, count);
            }
        }

        #endregion



        #region ELEMENTS MANIPULATION (protected)

        protected void InternalAddItem(T item)
        {
            EnsureCapacity(count + 1);
            ++count;    
            ++lastIndex;
            ar[lastIndex-firstIndex] = item;
        }


        protected void InsertElement(int index, T item)
        {
            if (index >= firstIndex && index <= lastIndex)
            {
                EnsureCapacity(count + 1);
                int intIndex = index - firstIndex;
                Array.Copy(ar, intIndex, ar, intIndex + 1, count - intIndex);
                ar[intIndex] = item;
                ++count;  ++lastIndex;
            }
            else if (index == lastIndex+1 && count > 0)
            {
                InternalAddItem(item);
            }
            else
            {
                throw new IndexOutOfBoundsException(index, 0, count);
            }
        }


        protected void RemoveLastElement()
        {
            if (count > 0)
            {
                --lastIndex;
                ar[--count] = default(T);
            }
            else
                throw new CollectionIsEmptyException();
        }


        protected void RemoveFirstElement()
        {
            if (count == 1)
            {
                ar[0] = default(T);
                count = 0;
                --lastIndex;
            }
            else if (count >= 2)
            {
                ar[0] = default(T);
                Array.Copy(ar, 1, ar, 0, count-1);
                ar[--count] = default(T);
                --lastIndex;
            }
            else
                throw new CollectionIsEmptyException();
        }


        protected void RemoveElementAt(int index)
        {
            if (index == firstIndex)
            {
                RemoveFirstElement();
            }
            else if (index > firstIndex && index <= lastIndex - 1)
            {
                int intIndex = index - firstIndex;
                ar[intIndex] = default(T);
                Array.Copy(ar, intIndex + 1, ar, intIndex, count - intIndex - 1);
                --lastIndex;
                ar[--count] = default(T);
            }
            else if (index == lastIndex)
            {
                RemoveLastElement();
            }
            else
            {
                if (IsEmpty)
                    throw new CollectionIsEmptyException();
                else
                    throw new IndexOutOfBoundsException(index, 0, count - 1);
            }
        }


        protected BT[] ListAllElements<BT>()
        {
            Debug.Assert( typeof(BT).IsAssignableFrom(typeof(T)) );

            BT[] result = new BT[count];
            if (count > 0)
                Array.Copy(ar, result, count);

            return result;
        }


        #endregion



        #region INTERFACE METHODS IMPLEMENTATION

        /// <summary>
        /// Removes all elements from the collection.
        /// </summary>
        public virtual void Clear()
        {
            if (ar != null && count > 0)
                for (int i = count - 1; i >= 0; i--)
                    ar[i] = default(T);
            ar = null;
            lastIndex = firstIndex - 1;
            count = 0;
        }


        /// <summary>
        /// Count of elements in the list.
        /// </summary>
        public int Count
        {
            get { return count; }
        }


        /// <summary>
        /// Checks whether the collection is empty.
        /// </summary>
        public bool IsEmpty
        {
            get { return count == 0; }
        }


        /// <summary>
        /// Checks whether the collection has at least one element.
        /// </summary>
        public bool IsNotEmpty
        {
            get { return count > 0; }
        }


        /// <summary>
        /// The first element of the list.
        /// </summary>
        /// <remarks>
        /// <p>Represents the first element of the collection.</p>
        /// </remarks>
        /// <exception cref="CollectionIsEmptyException">when collection is empty.</exception>
        public T First
        {
            get
            {
                if (count >= 1)
                    return ar[0];
                else
                    throw new CollectionIsEmptyException();
            }
        }

        /// <summary>
        /// The last element of the list.
        /// </summary>
        /// <remarks>
        /// <p>Represents the last element of the collection.</p>
        /// </remarks>
        /// <exception cref="CollectionIsEmptyException">when collection is empty.</exception>
        public T Last
        {
            get
            {
                if (count >= 1)
                    return ar[count - 1];
                else
                    throw new CollectionIsEmptyException();
            }
        }


        /// <summary>
        /// The first (low bound) index.
        /// </summary>
        public int FirstIndex
        {
            get { return firstIndex; }
        }


        /// <summary>
        /// The last (high bound) index.
        /// </summary>
        public int LastIndex
        {
            get { return lastIndex; }
        }


        /// <summary>
        /// Looks for a first occurence of the specified element and return an index
        /// of the found element.
        /// </summary>
        /// <para>
        /// Complexity of this function is <b><i>O(n)</i></b>.
        /// </para>
        /// <param name="elem">element to look for.</param>
        /// <returns>index of the found element, or <c>int.MinValue</c> if not found.</returns>
        public int IndexOf(T elem)
        {
            int found = Array.IndexOf(ar, elem, 0, count);
            return (found >= 0) ? firstIndex + found : int.MinValue;
        }


        public int IndexOf(Predicate<T> predicate)
        {
            return IndexOf(predicate, firstIndex);
        }


        public int IndexOf(Predicate<T> predicate, int startFromIndex)
        {
            int offset = CalcInternalIndex(startFromIndex);
            for (int i = offset; i < count; i++)
                if (predicate(ar[i]))
                    return firstIndex + i;
            return int.MinValue;
        }


        /// <summary>
        /// Checks whether the specified element contains in the collection.
        /// <para>
        /// Complexity of this function is <b><i>O(n)</i></b>.
        /// </para>
        /// </summary>
        /// <param name="elem">element for look for.</param>
        /// <returns>element existance.</returns>
        public virtual bool Contains(T elem)
        {
            if (ar != null)
                return Array.IndexOf(ar, elem, 0, count) >= 0;
            else
                return false;
        }


        /// <summary>
        /// Provides an access to a random element, 
        /// specified by index in the array.
        /// </summary>
        /// <param name="index">Element's index. 
        ///     Should be from the <c>FirstIndex</c> to the <c>LastIndex</c>, inclusive.</param>
        /// <returns>Element.</returns>
        /// <exception cref="CollectionIsEmptyException">is the collection is empty.</exception>
        /// <exception cref="IndexOutOfBoundsException">when index is out of bounds.</exception>
        public T this[int index]
        {
            get
            {
                int intIndex = CalcInternalIndex(index);
                return ar[intIndex];
            }
        }


        /// <summary>
        /// Looks for the first item that meets the specified predicate.
        /// </summary>
        /// <param name="predicate">item predicate.</param>
        /// <returns>found item, 
        ///          or a default value of the <typeparamref name="T"/> if not found.</returns>
        /// <seealso cref="Find"/>
        T RCollection<T>.this[Predicate<T> predicate]
        {
            get { return Find(predicate, default(T)); }
        }


        /// <summary>
        /// Looks for the first item that meets the specified predicate.
        /// </summary>
        /// <param name="predicate">item predicate.</param>
        /// <param name="defaultValue">default value, 
        ///                            that will be used in case 
        ///                            when no items meet the specified <paramref name="predicate"/>.</param>
        /// <returns>found item, or the specified <paramref name="defaultValue"/> if not found.</returns>
        public T Find(Predicate<T> predicate, T defaultValue)
        {
            for (int i = 0; i < count; i++)
                if (predicate(ar[i]))
                    return ar[i];
            return defaultValue;
        }


        /// <summary>
        /// Checks the argument and calculates internal index for the specified client index.
        /// </summary>
        /// <param name="index">client index (from FirstIndex to LastIndex).</param>
        /// <returns>internal zero-based index.</returns>
        protected int CalcInternalIndex(int index)
        {
            if (count == 0)
                throw new CollectionIsEmptyException();
            if (index < firstIndex || index > lastIndex)
                throw new IndexOutOfBoundsException(index, firstIndex, lastIndex);

            return index - firstIndex;
        }


        /// <summary>
        /// Excludes the last element from the list and returns it.
        /// </summary>
        /// <returns>just excluded element.</returns>
        /// <exception cref="CollectionIsEmptyException">is the collection is empty.</exception>
        public T ExcludeLast()
        {
            if (IsEmpty)
                throw new CollectionIsEmptyException("Attempted to exclude last item from an empty array-based collection.");

            T theLastElem = Last;
            RemoveLastElement();
            return theLastElem;
        }


        /// <summary>
        /// Returns all elements (that are contained in this collection) as an array.
        /// </summary>
        /// <returns>Array with elements. 
        ///          This array is zero-based even if the first index of the collection is not sero.
        ///          The order of elements is stable.
        ///          If the collection is empty an empty array is returned.
        /// </returns>
        public T[] ListAllElements()
        {
            T[] results = new T[count];
            if (count > 0)
                Array.Copy(ar, results, count);
            return results;
        }

        #endregion



        #region INTERNAL SUPPORT METHODS

        /// <summary>
        /// Sets the element into the specified cell. 
        /// Accepts an internal index started with 0 indepenedent of real lower bound.
        /// </summary>
        /// <param name="intIndex">internal index started with 0.</param>
        /// <param name="elem">element to set into collection.</param>
        internal void SetElement0(int intIndex, T elem)
        {
            if (!(0 <= intIndex && intIndex < count))
                throw new IndexOutOfBoundsException(firstIndex + intIndex, firstIndex + 0, firstIndex + count - 1);

            ar[intIndex] = elem;
        }


        /// <summary>
        /// Gets the element specified by it's cell index.
        /// Accepts an internal index started with 0 indepenedent of real lower bound. 
        /// </summary>
        /// <param name="intIndex">internal index started with 0.</param>
        /// <returns>got element.</returns>
        internal T GetElement0(int intIndex)
        {
            if (!(0 <= intIndex && intIndex < count))
                throw new IndexOutOfBoundsException(firstIndex + intIndex, firstIndex + 0, firstIndex + count - 1);

            return ar[intIndex];
        }

        #endregion



        #region ADDITIONAL FUNCTIONS

        /// <summary>
        /// Looks for an item that meets the given predicate.
        /// </summary>
        /// <param name="predicate">predicate.</param>
        /// <returns>the first found item, or a default value if not found.</returns>
        public T this [Func<T,bool> predicate]
        {
            get
            {
                for (int i = 0; i < count; i++)
                    if (predicate(ar[i]))
                        return ar[i];
                return default(T);
            }
        }


        /// <summary>
        /// Looks for an item of the specified class 
        /// meets the given predicate.
        /// </summary>
        /// <typeparam name="X">class of item to look for.</typeparam>
        /// <param name="predicate">predicate for an item.</param>
        /// <param name="notFound">vaue will be returned if not found.</param>
        /// <returns>found item or <paramref name="notFound"/> if not found.</returns>
        public X Find<X> (Func<X,bool> predicate, X notFound)
            where X: class, T
        {
            for (int i = 0; i < count; i++)
                if (ar[i] is X)
                {
                    X candidate = ar[i] as X;
                    if (predicate(candidate))
                        return candidate;
                }

            return notFound;
        }


        /// <summary>
        /// Looks for an item of the specified class 
        /// meets the given predicate.
        /// </summary>
        /// <typeparam name="X">class of item to look for.</typeparam>
        /// <param name="predicate">predicate for an item.</param>
        /// <returns>found item or null if not found.</returns>
        public X Find<X> (Func<X,bool> predicate)
            where X: class, T
        {
            return Find(predicate, null);
        }

        #endregion



        #region ITERATOR

        /// <summary>
        /// Creates a new read-only iterator.
        /// </summary>
        /// <returns>iterator.</returns>
        RIterator<T> RCollection<T>.TakeIterator()
        {
            return new Iterator<T>(this);
        }

        /// <summary>
        /// Creates a new read-only iterator.
        /// </summary>
        /// <returns>iterator.</returns>
        public WIterator<T> TakeIterator()
        {
            return new Iterator<T>(this);
        }



        System.Collections.Generic.IEnumerator<T> System.Collections.Generic.IEnumerable<T>.GetEnumerator()
        {
            return new Iterator<T>(this);
        }

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return new Iterator<T>(this);
        }


        /// <summary>
        /// Writeable iterator.
        /// </summary>
        /// <typeparam name="TT"></typeparam>
        internal class Iterator<TT>
            : WIterator<TT>,
              System.Collections.Generic.IEnumerator<TT>,
              System.Collections.IEnumerator
        {
            private readonly ArrBaseCollection<TT> col;
            private int intIndex;
            private sbyte where;

            internal Iterator(ArrBaseCollection<TT> col)
            {
                this.col = col;
                Reset();
            }

            internal Iterator(ArrBaseCollection<TT> col, int intIndex, sbyte where)
            {
                this.col = col;
                this.intIndex = intIndex;
                this.where = where;
            }

            public void Reset()
            {
                intIndex = int.MinValue;
                where = -1;
            }

            public bool Next()
            {
                switch (where)
                {
                    case -1:
                        if (col.IsNotEmpty)
                        {
                            where = 0;
                            intIndex = 0;
                        }
                        else
                        {
                            where = +1;
                            intIndex = int.MaxValue;
                        }
                        break;
                    case 0:
                        if (intIndex < col.count-1)
                        {
                            intIndex++;
                        }
                        else
                        {
                            where = +1;
                            intIndex = int.MaxValue;
                        }
                        break;
                    case 1:
                        throw new OutOfCollectionException("Iterator reaches the end of collection.");
                }

                return where == 0;
            }


            /// <summary>
            /// Represents where the current position of the iterator.
            /// </summary>
            /// <remarks>
            /// Possible value:
            /// <list type="bullet">
            /// <item>-1: before the first item;</item>
            /// <item>0: at an item of the collection;</item>
            /// <item>+1: behind the last item.</item>
            /// </list>
            /// </remarks>
            public sbyte Where
            {
                get { return where; }
            }


            public WIterator<TT> Clone()
            {
                return new Iterator<TT>(col, intIndex, where);
            }

            RIterator<TT> RIterator<TT>.Clone()
            {
                return Clone();
            }


            TT RIterator<TT>.Current
            {
                get { return col.ar[intIndex]; }
            }


            public TT Current
            {
                get { return col.ar[intIndex]; }
                set { col.ar[intIndex] = value; }
            }

            public TT Exclude()
            {
                TT elem = Current;
                col.RemoveElementAt(intIndex);
                return elem;
            }



            TT System.Collections.Generic.IEnumerator<TT>.Current
            {
                get { return col.ar[intIndex]; }
            }

            object System.Collections.IEnumerator.Current
            {
                get { return col.ar[intIndex]; }
            }

            bool System.Collections.IEnumerator.MoveNext()
            {
                if (where < +1)
                    return Next();
                else
                    return false;
            }

            public void Dispose() { }
        }

        #endregion
        
        
    }


    #region DEBUG HELPER

    /// <summary>
    /// Debug helper.
    /// </summary>
    internal class ArrBaseCollectionDebugView<T>
    {
        private readonly ArrBaseCollection<T> list;


        public ArrBaseCollectionDebugView(ArrBaseCollection<T> list)
        {
            this.list = list;
        }


        [DebuggerBrowsable(DebuggerBrowsableState.RootHidden)]
        public Array Items
        {
            get
            {
                if (list != null && list.IsNotEmpty)
                    return DebugViewUtils.MakeArray(list.ar,
                                                    list.firstIndex,
                                                    list.count);
                else
                    return new T[0];
            }
        }
    }

    #endregion

}
